A global computer network such as the Internet can be conceptualized as one huge network encompassing scores of smaller networks. The data transfers that take place between these scores of smaller networks are made possible through a hierarchy of communications layers utilizing a variety of communications protocols. A protocol is a set of conventions or rules that govern the transfer of data between network devices. Rudimentary protocols typically define only a hardware configuration, while protocols that are more complex define data formats, timing, error detection/correction procedures, and software structures. The seven-layer Open Systems Interconnect (OSI) Reference Model developed by the International Standards Organization (ISO), and extensively articulated in the literature, is generally used to describe the structure and function of data communications protocols. A considerable role of each layer in the OSI model is to supply services to the other layers. Connection-oriented and connectionless network services are two of the types of services provided by the OSI layers.
In a connection-oriented service, a source node creates a connection with a destination node and, after transmitting a data packet, terminates the connection. The overhead related to setting up the connection might be unappealing in the case of nodes that require very efficient communication operations. In this case, a fully connectionless service is preferable. With a connectionless service, each transmitted data packet carries the full address of its destination through the network. The destination address is used by the network layer protocols to determine the route or path of the data packet. Connectionless network services are generally implemented in network layer protocols that perform basic connectionless service, neighbor greeting, and routing functions. The basic connectionless service functions are primarily concerned with data packet formatting and end node status notification, e.g., error messages. The neighbor greeting function enables end nodes to determine which routers are available on their local network, while enabling routers to determine their end node neighbors.
A simplified example of a distributed network system is shown in FIG. 1, and is referred to as internetwork system 100. Internetwork system 100 may contain various routing domains 103, 105, and 107, which are tied to a backbone network 101. In a hierarchically arranged distributed network system 100, backbone 101 is the central connection path shared by the nodes and networks connected to it. The backbone 101 administers the bulk of traffic between communicating nodes to provide end-to-end service between one user, for example source node 122 in domain 103, and another user, for example destination node 142 in domain 107. Each routing domain 103-107 in internetwork system 100 is a collection of one or more local networks 120, 125, 130, 135, 140 that are attached to the backbone 101 through one or more routers 123, 132, and 134. In the following discussion, the term “local network” shall be used to refer to all types of networks that may be included in a domain. Routing domains 103-107 are also referred to as customer networks or autonomous systems (AS), however the term autonomous system is used more often than “routing domain” within the Internet community and in the Internet Protocol Suite, or IP. An autonomous system is a set of nodes and routers that operate under the same administration.
The networks in routing domains 103-107 may be local area networks (LAN), wide area networks (WAN), metropolitan area networks (MAN), or the like, all of which are attached to backbone 101 through routers 109, 111, and 113. A router is a specialized computer for processing IP data and forwarding IP data along respective network paths. In FIG. 1, a local network is shown as a horizontal line to which end nodes, such as node 122 on local network 120, or node 137 on local network 135, can be attached. Nodes are depicted by a circle with an ‘N’ within the circle, and are connected to their respective local networks. If a node is attached to the horizontal line representing a network, that node can transmit data to, and receive data from, every other node attached to the same horizontal line. Source and destination nodes are generally computer workstations and/or servers, but may be any type of device that can include a network interface card, such as a printer, modem, or facsimile machine.
The routing protocols implemented in routers 109, 111, and 113 are referred to as interdomain routing protocols, or exterior gateway protocols (EGP). One example of an exterior gateway protocol is the Border Gateway Protocol (BGP; RFC 1771), which is used to provide loop-free interdomain routing between autonomous systems. Interdomain routers 109, 111, and 113 thus encompass a higher routing level in distributed internetwork system 100. The simplified example of FIG. 1 does not show more than one interdomain router connecting each domain 103-107 to backbone 101, however, it should be noted that oftentimes more than one interdomain router is used to connect domains to the backbone, for purposes of redundancy.
The routing protocols implemented in routers 123, 132, and 134 are referred to as intradomain routing protocols, or interior gateway protocols (IGP). Examples of an interior gateway protocol are routing information protocol (RIP), open shortest path first (OSPF), and NetWare link services protocol (NLSP; from Novell, Inc.), among various others. Intradomain routers 123, 132, and 134 encompass a lower routing level in distributed internetwork system 100, and are tasked with managing communications between local networks and nodes within their respective domains 103-107. The interdomain routers manage all of the intradomain routers without addressing details internal to lower routing levels. Communications amongst these routers generally comprises an exchange (i.e., an advertising) of routing information. This exchange occurs between routers at the same routing level (peer routers), as well as between routers at different routing levels.
Although the majority of Internet users have never seen a router, the functions performed by this specialized computer are largely responsible for allowing the Internet (or any other large internetwork such as hierarchically arranged distributed network system 100) to exist. Routing and the information routers exchange may be considered the “glue” that binds distributed networks together. Without routers and routing, IP traffic would be limited to a single physical network. IP routing specifies that IP packets (datagrams) travel through internetworks one hop at a time (next hop routing) based on the destination address in the IP header. The entire route is not known at the outset of the journey. Instead, at each stop, the next router or destination end node (referred to as the next hop) is calculated by matching the destination address within the datagram's IP header with an entry in the current node's (typically, but not always, a router) routing table. Alternately, a route policy may be used instead of routing table entries to derive the next hop address. As more nodes are added to an IP network, the amount of routing information that must be shared (exchanged) between routers increases, as does the size of the routers' configuration or routing tables. A routing or configuration table is a collection of information that a router uses to decide where a packet should go (which network path to take), and includes information such as which connections lead to a particular address, priorities for connections to be used, and rules to use for handling routine and special cases of packet traffic, etc.
A network with a limited number of gateways to other TCP/IP networks can be configured with static routing. A static routing table is constructed manually by the network administrator using the ip route command via a command language interface (CLI) to the router(s). Static routing tables do not adjust to network topology changes, so static routing tables should only be used where the topology seldom changes. In the case where remote destinations can only be reached through one route, however, a static route is generally the best routing choice. When there is more than one possible route to the same destination, dynamic routing is recommended. A dynamic routing table is constructed from the information exchanged by routing protocols, which are designed to distribute information that dynamically adjusts routes to reflect changing network topology conditions. Routing protocols can manage complex routing situations more efficiently and accurately than the network administrator can.
Improvements in router processing power and in the development of routing protocols and other techniques such as aggregation of routes have been used to reduce the amount of routing information that needs to be shared between routers. Aggregation is the process of combining several different routes in such a way that a single route can be advertised. For example, an aggregate route can be considered a route in which only an IP subnet address for each route needs to be considered for routing purposes. Advertising an aggregate route means exchanging or providing information about the aggregate route to other routers. Aggregation serves the purpose of minimizing the size of routing tables used to store advertised IP routes. This concept is demonstrated in FIG. 2, which shows a simple aggregate route being advertised from one router to another router.
In FIG. 2, router B 215, shares routing information with another router A 210, in the form of an autonomous system (AS) external link state advertisement (LSA) message 220. Thus router B 215 is utilizing a link-state protocol, in the example presented, OSPF, in which a link can be considered as being an interface on router B 215. The state of the link is a description of that interface, and of its relationship to its neighboring routers, such as router A 210. A description of the interface could include, for example, the IP address of the interface, the mask, the type of network it is connected to, the routers connected to that network, and the like. The compilation of all these link-states forms a link-state database (not illustrated).
LSA message 220 contains the IP address of an aggregate route, i.e., 1.1.0.0/16. In the example of FIG. 2, the aggregate route information provided by server B 215 is obtained from server B's 215 access to three separate servers, server 217, server 218, and server 219, at IP addresses 1.1.1.1, 1.1.2.2, and 1.1.3.3, respectively.
The various types of routers follow routing models, e.g., GateD derivations or RouteD derivations, and each routing protocol can be a source of information. That routing information can be subjected to import policies, which affect whether or not the information will enter the Routing Information Base (RIB). Import policies may not be applied to routes representing directly connected interfaces, static routes, and aggregate routes. These directly connected interfaces, static routes, and aggregate routes will be in the RIB for as long as they are valid. The RIB contains all routes that are valid and are not rejected by an import policy. Typically, the RIB contains multiple routes to the same prefix (e.g., the number of leading bits in an IP address which represents the net number portion of the IP address, for example, the IP address bits common to the IP addresses occurring within a subnet), but from different protocol sources.
In the case of multiple routes to the same prefix, the router needs to decide which source (of the same information) will be considered more “trustworthy” than others will, that is, there is a measure of preference between different routing protocols. Each routing protocol is assigned a default preference value, which can be modified when configuring a router. The route selection process, with the help of route preference, chooses the active routes from the RIB, and copies them into the Forwarding Information Base (FIB). The FIB is used for packet forwarding, and contains straightforward mapping between prefixes and next hops to be used for those prefixes.
Export policies can be applied to the active routes in the FIB to control which of those will be exported (distributed, or in the vernacular of the art, redistributed) to other routing protocols. Unlike import policies, export policies can be applied to prefixes from any source, including connected, static, and aggregate routes. Redistribution can be considered a “shortcut” means of configuring an export policy. As an export policy, redistribution takes active routes from the RIB that originate from a given source protocol, and advertises them to a target protocol.
FIG. 3 is a simplified diagram showing the generation of an autonomous system (AS) external link state advertisement (LSA) message such as AS external LSA message 220 discussed in FIG. 2. The generation of external LSA message 220 involves a configuration interface 310 such as command language interface (CLI) within router B 215. A user, e.g., network operator, system administrator, etc., inputs the various commands into a console 315, typically via a keyboard, which console 315 transmits to the CLI configuration interface 310. The CLI configuration interface 310 then instructs an open shortest path first (OSPF) routing protocol process 305 running on router B 215 to generate the message according to the received input from user at console 315. The commands input in the example of FIG. 3 are shown in sample input commands area 316.
In the example of FIG. 3, operator sample input commands 316 are provided for distributing three aggregate routes, IP route 1.1.0.0/16, IP route 2.2.0.0/16, and IP route 3.3.0.0/16. Each of the aggregate routes also requires the operator to provide a next-hop address 320 in the input commands 316 for the respective aggregate routes. In FIG. 3, for example, the next-hop address 320 of 1.1.1.1 is provided by the user for aggregate route 1.1.0.0/16, the next-hop address 320 of 2.2.1.0 if provided by the user for aggregate route 2.2.0.0/16, and the next hop address 320 of 3.3.1.2 is provided by the user for aggregate route 3.3.0.0/16. A next hop address 320 is an address of one of the devices accessible by the aggregate route. Each aggregate route must have a next hop address such as 320 that is reachable through Router B 215. For example, in the simple model illustrated in FIG. 2, the aggregate route 1.1.0.0/16 could specify a next hop address of 1.1.1.1, or 1.1.2.2, or 1.1.3.3—only one next hop address is required even though an IP subnet (i.e., 1.1.0.0/16) can be reached through three different device addresses.
The aggregate routes must be added as static routes and then redistributed into OSPF 305. When route redistribution is invoked, all static routes in Router B 215 are redistributed over to Router B's 215 neighbors. A redistribution policy 330 must be used to filter out all unwanted static routes from being redistributed into OSPF 305. To this end, the user creates a route map which specifies a redistribution policy 330 required by the redistribute static command, as is illustrated in an exemplary manner in the commands area 316. The route map is a means of controlling the (re)distribution of routes between routing domains. The syntax and/or purpose of these various commands are well-known in the art, and will therefore not be discussed in detail.
One problem with the prior art such as the example presented in FIG. 3 is that each static route representing an aggregate route requires a user to provide a next hop address in the CLI/router configuration process. As previously stated, however, a next hop address is only one of the device addresses reachable via the aggregate route. However, should the device specified as the next hop address become unavailable, i.e., be out of service for whatever reason, the entire aggregate route is adversely affected. For example, if the next hop address 320 of 1.1.1.1 is out of service, the static route with IP subnet 1.1.0.0/16 is no longer reachable because it does not have a reachable next hop address 320. This static route would be removed from the routing table in Router B 215, and OSPF 305 in Router B 215 would send another AS external LSA message 220 informing its neighbors that 1.1.0.0/16 is no longer reachable, even if numerous other devices are still in service with addresses within IP subnet 1.1.0.0/16, i.e., 1.1.2.2, or 1.1.3.3, etc. No other routers in the network know about 1.1.2.2 and 1.1.3.3 because the subnet address 1.1.0.0/16 is no longer advertised by Router B 215 should the specified next hop address 320 go out of service. That is, advertisement of the aggregate route to other routers will be suspended for as long as the unavailability of the device specified as the next hop address persists, thereby rendering other devices subtending from the aggregate route unreachable, and potentially disrupting a large portion of the routes in a segment or segments of IP networks.
Another problem with the prior art as regards a user having to manually provision a next hop address is the amount of time often required of a user to do so, which can be considerable in the case of numerous entries. In addition, there is a possibility of the user inadvertently introducing errors when entering the next-hop address via the CLI, e.g., entering x.z.x.x instead of x.x.x.x for the next-hop address. Correction of entry errors is also time consuming, and may render portions of a network unreachable until the entry error is corrected.
Therefore, what is needed is a method for distributing aggregate routes that overcomes the problems inherent when a user must manually provision a next hop address.